/*
 * 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4
 

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000
 * 
 */
/*
 * 思路：判断三角形 ：运用两边之和大于第三边来确定是否能构成三角形
 * 1.先给数组排序
 * 2.固定最右边i，用left标记最左边，right标记最右边
 * 3.判断nums[left]+nums[right]是否大于nums[i]
 * 4.若小于，则left++,若大于，则三角形数量加right-left，然后right--
 * 5.循环2~4，直到循环条件不满足
 */

 class Solution {
    public int triangleNumber(int[] nums) {
        int res=0;
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=n-1;i>1;i--){
            int left=0;//最左边
            int right=i-1;//最右边-1
            while(left<right){
                int sum=nums[left]+nums[right];//较小两边之和
                if(sum<=nums[i]){
                    left++;
                }else{
                    res+=right-left;
                    right--;
                }
            }
        }
        return res;
    }
}